package DoublePointer;    /**
     * 4. 回文字符串
     * 680. Valid Palindrome II (Easy)
     * Input: "abca"
     * Output: True
     * Explanation: You could delete the character 'c'.
     * 题目描述：可以删除一个字符，判断是否能构成回文字符串。
     *
     * 所谓的回文字符串，是指具有左右对称特点的字符串，例如 "abcba" 就是一个回文字符串。
     *
     * 使用双指针可以很容易判断一个字符串是否是回文字符串：令一个指针从左到右遍历，
     * 一个指针从右到左遍历，这两个指针同时移动一个位置，每次都判断两个指针指向的字符是否相同，
     * 如果都相同，字符串才是具有左右对称性质的回文字符串。
     */

    import java.util.ArrayList;

    /**
     * 本题的关键是处理删除一个字符。在使用双指针遍历字符串时，如果出现两个指针指向的字符不相等的情况，
     * 我们就试着删除一个字符，再判断删除完之后的字符串是否是回文字符串。
     *
     * 在判断是否为回文字符串时，我们不需要判断整个字符串，
     * 因为左指针左边和右指针右边的字符之前已经判断过具有对称性质，所以只需要判断中间的子字符串即可。
     *
     * 在试着删除字符时，我们既可以删除左指针指向的字符，也可以删除右指针指向的字符。
     */
    public class DobluePointer4_Palindrome {
        public static void main(String[] args) {

            
            String str = "abcbfa";
            int left , right;
            boolean palindrome1 = true;
            boolean palindrome2 = true;
            String result = null;
            for (left=0,right=str.length()-1;left<right;left++,right--){
                //发现不是回文的字符，删掉该字符，继续进行判断
                if (str.charAt(left)!=str.charAt(right)){
                    //尝试删除左边，尝试删除右边，发现删除左边后，得到的字符串是回文的
                     palindrome1 = isPalindrome(str, left+1, right);
                     palindrome2 = isPalindrome(str, left, right-1);

                     //获得删除后的回文字符串后，终止循环执行
                     break;
                }
            }
            //根据删除字符情况，输出最终的回文字符串
            if (palindrome1){
                String substring_left = str.substring(0, left);
                String substring_right = str.substring(left + 1, str.length());
                 result = substring_left.concat(substring_right);
            }
            if (palindrome2){
                String substring_left = str.substring(0, right);
                String substring_right = str.substring(right + 1, str.length());
                result = substring_left.concat(substring_right);
            }
            System.out.println(result);
            System.out.println(palindrome1);
            System.out.println(palindrome2);

        }
        public static boolean isPalindrome(String str,int left,int right){

            while (left<right) {
                if (str.charAt(left)==str.charAt(right)){
                    left++;
                    right--;
                }else {
                    return false;
                }
            }
            return true;
        }

    }
